package algorithm;

import conmon.BasicConstant;

/**
 * @Description //快速排序
 * @Author Administrator
 * @DATE 2020/11/1 15:25
 **/
public class Quick {

    public static void quick(int[] arr, int lIndex, int rIndex) {
        if (lIndex < rIndex) {
            //基准数
            int i = lIndex, j = rIndex, x = arr[lIndex];
            while (i < j) {
                //1.1先从右边开始遍历， arr[j] >= x ，如果右边大于基准数，向左移动
                while (i < j && arr[j] >= x) {
                    j--;
                }
                //1.2 此时右边小于基准数，此时把 arr[j] 给左边的数，并且 i 向右移动（i++）
                if (i < j) {
                    arr[i] = arr[j];
                    i++;
                }

                //2.1 再从左边开始遍历， arr[i] < x ，如果左边小于基准数，向右移动
                while (i < j && arr[i] < x) {
                    i++;
                }
                //2.2 此时左边大于基准数，把 arr[i] 给 右边的位置，并且 j 向左移动(j--)
                if (i < j) {
                    arr[j] = arr[i];
                    j--;
                }
            }
            //3.1经过几轮的遍历，此时 i 已经 >=j ，完成初步将 基准数放置相对中间的位置
            arr[i] = x;
            //3.2 接下来就是将 i 左边的数组 和 右边的数组分别遍历，递归调用
            quick(arr, lIndex, i - 1);
            quick(arr, i + 1, rIndex);
        }
    }

    public static void main(String[] args) {
        quick(BasicConstant.ARR, 0, BasicConstant.ARR.length - 1);
    }
}
